package com.yangli.leecode.mashib;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Description https://www.bilibili.com/video/BV1rK411U7VD?p=56&vd_source=ee264bd7d696e9474b767a0b28f15164
 * @Author liyang
 * @Date 2023/1/28 17:28
 */
public class Interview {
    public static void main(String[] args){
        Interview interview = new Interview();
        System.out.println(interview.findTarget(new int[]{1, 2, 3}, 2));

        System.out.println(interview.findTarget4(new int[]{1, 1, 1}, 1));

    }


    //https://leetcode.cn/problems/target-sum/
    //暴力递归
    public int findTarget(int[] arr, int target){
        if (arr.length == 0) {
            return 0;
        }
        return process(arr, 0, target);
    }

    public int process(int[] arr, int index, int rest){
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        return process(arr, index + 1, rest + arr[index]) + process(arr, index + 1, rest - arr[index]);
    }

    //增加缓存 记忆化搜索
    public int findTarget2(int[] arr, int target){
        if (arr.length == 0) {
            return 0;
        }
        Map<String, Integer> cache = new HashMap<>();
        return process(arr, 0, target, cache);
    }

    public int process(int[] arr, int index, int rest, Map<String, Integer> cache){
        if (cache.containsKey(index + "_" + rest)) {
            return 1;
        }
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        return process(arr, index + 1, rest + arr[index]) + process(arr, index + 1, rest - arr[index]);
    }

    /**
     * 题目的几个优化
     * 1，数字如果有负数，全部转成正数，不影响结果。
     * 2.
     */
    public int findTarget3(int[] arr, int target){
        if (arr.length == 0) {
            return 0;
        }
        int sum = Arrays.stream(arr).sum();
        int[][] dp = new int[arr.length + 1][sum * 2 + 1];
        dp[arr.length][sum] = 1;
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < 2 * sum + 1; j++) {
                if (j - arr[i] > 0) {
                    dp[i][j] += dp[i + 1][j - arr[i]];
                }
                if (j + arr[i] < 2 * sum + 1) {
                    dp[i][j] += dp[i + 1][j + arr[i]];
                }
            }
        }
        return dp[0][2 * target];
    }

    // 优化点一 :
    // 你可以认为arr中都是非负数
    // 因为即便是arr中有负数，比如[3,-4,2]
    // 因为你能在每个数前面用+或者-号
    // 所以[3,-4,2]其实和[3,4,2]达成一样的效果
    // 那么我们就全把arr变成非负数，不会影响结果的
    // 优化点二 :
    // 如果arr都是非负数，并且所有数的累加和是sum
    // 那么如果target<sum，很明显没有任何方法可以达到target，可以直接返回0
    // 优化点三 :
    // arr内部的数组，不管怎么+和-，最终的结果都一定不会改变奇偶性
    // 所以，如果所有数的累加和是sum，
    // 并且与target的奇偶性不一样，没有任何方法可以达到target，可以直接返回0
    // 优化点四 :
    // 比如说给定一个数组, arr = [1, 2, 3, 4, 5] 并且 target = 3
    // 其中一个方案是 : +1 -2 +3 -4 +5 = 3
    // 该方案中取了正的集合为P = {1，3，5}
    // 该方案中取了负的集合为N = {2，4}
    // 所以任何一种方案，都一定有 sum(P) - sum(N) = target
    // 现在我们来处理一下这个等式，把左右两边都加上sum(P) + sum(N)，那么就会变成如下：
    // sum(P) - sum(N) + sum(P) + sum(N) = target + sum(P) + sum(N)
    // 2 * sum(P) = target + 数组所有数的累加和
    // sum(P) = (target + 数组所有数的累加和) / 2
    // 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
    // 那么就一定对应一种target的方式
    // 也就是说，比如非负数组arr，target = 7, 而所有数累加和是11
    // 求有多少方法组成7，其实就是求有多少种达到累加和(7+11)/2=9的方法
    // 优化点五 :
    // 二维动态规划的空间压缩技巧
    public int findTarget4(int[] arr, int target){
        int sum = 0;
        for (int n : arr) {
            sum += n;
        }
        return sum < target || ((target & 1) ^ (sum & 1)) != 0 ? 0 : subset2(arr, (target + sum) >> 1);

    }

    //求数组的子集个数==>一般求个数都是用动态规划
/*    public int findSum(int[] arr, int sum){
        if (sum < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][sum + 1];
        dp [0][0] = 1;
        for (int num : arr) {
            for (int i = num; i <; i++) {
                dp
            }
        }
    }*/


    // 求非负数组nums有多少个子集，累加和是s
    // 二维动态规划
    // 不用空间压缩
    public static int subset1(int[] nums, int s){
        if (s < 0) {
            return 0;
        }
        int n = nums.length;
        // dp[i][j] : nums前缀长度为i的所有子集，有多少累加和是j？
        int[][] dp = new int[n + 1][s + 1];
        // nums前缀长度为0的所有子集，有多少累加和是0？一个：空集
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= s; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][s];
    }

    // 求非负数组nums有多少个子集，累加和是s
    // 二维动态规划
    // 用空间压缩:
    // 核心就是for循环里面的：for (int i = s; i >= n; i--) {
    // 为啥不枚举所有可能的累加和？只枚举 n...s 这些累加和？
    // 因为如果 i - n < 0，dp[i]怎么更新？和上一步的dp[i]一样！所以不用更新
    // 如果 i - n >= 0，dp[i]怎么更新？上一步的dp[i] + 上一步dp[i - n]的值，这才需要更新
    public static int subset2(int[] nums, int s){
        if (s < 0) {
            return 0;
        }
        int[] dp = new int[s + 1];
        dp[0] = 1;
        for (int n : nums) {
            for (int i = s; i >= n; i--) {
                dp[i] += dp[i - n];
            }
        }
        return dp[s];
    }

}
